A method and system has been invented that allow for image segmentation in the case of more than two labels using a novel graph cut model.
The method is based on graphs that have the form of undirected flow networks. The flow network is an undirected weighted graph, G is defined as a set of nodes or vertices V, a set of edges E and a positive weight function, w associated with the edges:G=(V,E) and w:E→R+  (1)where each edge, {p, q} is defined as a pair of nodes p, q∈V. Additionally, a subset of the nodes, L are “label” nodes.
A graph cut, C is defined as a subset of the edges in the graph such that when those edges are removed from the graph the remaining graph consists of |L| connected components and each connected component contains one node from the set L
A minimum-weight graph cut or minimum cut is a graph cut that has a minimum weight of all the possible graph cuts:
                              C          min                =                                            arg              ⁢                                                          ⁢              min                                      C              ∈              χ                                ⁢                                    ∑                                                {                                      p                    ,                    q                                    }                                ∈                C                                      ⁢                          w              pq                                                          (        2        )            where χ is the set of all possible graph cuts.
An exact solution for the graph cut can be obtained for the case with binary labels. Methods for obtaining this solution are based on establishing a flow through the graph. All flows are allowed that conserve flow at each node and, for each edge in the graph, are less than the weight of the edge. Another approach is to establish flow through electrical network models. In these methods, an electrical network is defined using resistors that represent the weights at each edge in the graph. A competitive algorithm for obtaining the graph cut has arisen based on the electrical model. A novel methodology is presented here that generalizes prior methods to allow for image segmentation in the case of more than two labels.